package leetcode_数组.统计数组中的元素;

import java.util.Arrays;

// 缺失的第一个正数
public class _41 {
    public static void main(String[] args) {
        int[] ints = {7, 8, 9, 11, 12};
        System.out.println(firstMissingPositive1(ints));
    }

    // 快速排序的时间复杂度
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int ans = 1;
        for (int num : nums) {
            if (num > 0) {
                if (ans == num) {
                    ans += 1;
                }
            }
        }
        return ans;
    }

    public int firstMissingPositive_new(int[] nums) {
        // 长度为 n 的数组, 缺失的正整数肯定在 1 ~ n + 1 中
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) nums[i] = -n - 1;
            else nums[i] = -nums[i];
        }
        for (int i = 0; i < n; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (idx < n && nums[idx] < 0) nums[idx] =-nums[idx];
        }
        for (int i = 0; i < n; i++) if (nums[i] < 0) return i + 1;
        return n + 1;
    }

    // O(n)
    // 最小正数的范围在 [1, nums.length() + 1]
    public static int firstMissingPositive1(int[] nums) {
        // 把非正整数全部变为 l + 1
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] <= 0 ? nums.length + 1 : nums[i];
        }
        // 把 index 上的数变为负数，前提是 index + 1 表示的正整数出现过
        for (int i = 0; i < nums.length; i++) {
            int tem = Math.abs(nums[i]);
            if (tem > 0 && tem <= nums.length) {
                int newIndex = Math.abs(nums[i]) - 1;
                if (nums[newIndex] > 0) {
                    nums[newIndex] *= -1;
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

}
